/*
  生成由数字0～8组成的9x9矩阵，要求：
     每行都由0～8数字组成，每个数字有且仅有出现一次
     每列都由0～8数字组成，每个数字有且仅有出现一次
  TODO: 需要生成一个序列，每个元素为一个上面的矩阵，且每个矩阵中同一行相邻的两个值必须在之前的元素中未出现过
*/

#include <stdio.h>
#include <assert.h>
#include <algorithm>

const int N = 9;

int mate[N][N] = {0};
void print()
{
    printf("mate:\n");
    for (int i = 0; i < N; i++) {
        for (int k = 0; k < N; k++)
            printf("%4d,", mate[i][k]);
        printf("\n");
    }
}

void place(int colm)
{
    int num[N] = {0, 1, 2, 3, 4, 5, 6, 7, 8};

    if (colm >= N) {
        print();
        exit(0);
    }
    while(std::next_permutation(num, num + N)) {
        bool finished = true;
        for (int i = 0; i < N; i++) {
            for (int k = 0; k < colm; k++) {
                if (mate[i][k] == num[i])
                    finished = false;
            }
        }
        if (finished) {
            // printf("Column %d:\n", colm);
            for (int i = 0; i < N; i++) {
                mate[i][colm] = num[i];
                // printf("%4d", num[i]);
            }
            // printf("\n");
            place(colm + 1);
        }
    }
}

int main()
{
    place(0);
}
